package no57;

import java.util.HashSet;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/5/16 16:36
 * 和为 s 的两个数字
 * https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/
 */
public class Solution {

    // 方法一, 哈希思想, 时间复杂度 O(n), 空间复杂度 O(n)
    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2]; // 用于存储结果
        // 哈希表思想 时间复杂度O(n)
        HashSet<Integer> set = new HashSet<>();
        for(int i = 0; i < nums.length; i++) {
            int num = target - nums[i];
            if (set.contains(num)) {
                res[0] = num;
                res[1] = nums[i];
                break;
            }
            set.add(nums[i]);
        }
        return res;
    }

    // 方法二, 排序数组, 双指针, 空间复杂度 O(1)
    public int[] twoSum2(int[] nums, int target) {
        int i = 0, j = nums.length - 1;
        while(i < j) {
            int s = nums[i] + nums[j];
            if(s < target) i++;
            else if(s > target) j--;
            else return new int[] { nums[i], nums[j] };
        }
        return new int[0];
    }
}
